/*
 * @Description:
 * @Author: chenjiaxin
 * @Date: 2022-06-12 16:44:59
 * @LastEditTime: 2022-06-19 15:24:59
 * @FilePath: \leetcode\4_双向链表\01_双向链表的封装.js
 */
function DoublyLinkedList() {
  // 内部节点类
  function Node(data) {
    this.data = data;
    this.prev = null; // previous 缩写 指向上一个节点
    this.next = null;
  }

  // 属性
  this.head = null;
  this.tail = null; // 指向最后一个节点
  this.length = 0;

  // 方法
  /**
   * 1. 后面追加数据
   * @param {any} data
   */
  DoublyLinkedList.prototype.append = function (data) {
    // 1. 创建新的节点
    let newNode = new Node(data);
    // 2. 判断 是否第一个节点
    if (this.head == null) {
      // 2.1 第一个节点
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 2.2 不是第一个节点
      // let currentNode = this.head;
      // // 循环找到 最后的节点
      // while (currentNode.next) {
      //   currentNode = currentNode.next;
      // }
      // currentNode.next = newNode;
      // newNode.prev = currentNode;
      // this.tail = newNode;

      // 2.3 通过 tail 可以找到 最后一个节点  然后 在其后面 添加一个节点
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    // 3. length + 1
    this.length += 1;
  };

  /**
   * 2. 向后拼接数据
   * @returns
   */
  DoublyLinkedList.prototype.backwardString = function () {
    let currentNode = this.head;
    let resultString = "";
    while (currentNode) {
      resultString += currentNode.data + " ";
      currentNode = currentNode.next;
    }
    return resultString;
  };

  /**
   * 3. 向前拼接数据
   * @returns
   */
  DoublyLinkedList.prototype.forwardString = function () {
    let currentNode = this.tail;
    let resultString = "";
    while (currentNode) {
      resultString += currentNode.data + " ";
      currentNode = currentNode.prev;
    }
    return resultString;
  };

  /**
   * 4. 向后拼接数据
   * @returns
   */
  DoublyLinkedList.prototype.toString = function () {
    return this.backwardString();
  };

  /**
   * 5. 插入元素
   * @param {number} position : ;
   * @param {any} data
   */
  DoublyLinkedList.prototype.insert = function (position, data) {
    // 1. 边界判断(类型判断就不做了 推荐使用ts)
    if (position < 0 || position > this.length) {
      return false;
    }

    // 2. 创建节点
    let newNode = new Node(data);

    // 因为有 tail 属性 要指向最后一个元素 所以 考虑的情况要比当向链表多
    // 3. 判断链表是否为空
    if (this.length == 0) {
      // 链表为空 此时 position 不可能 > 0, 只能是 0
      this.head = newNode;
      this.tail = newNode;
    } else {
      // 链表有数据
      // 也得判断 是不是插入到最后一个  还是 第一个 还是中间 插入
      if (position == 0) {
        newNode.next = this.head;
        this.head.prev = newNode;

        this.head = newNode;
      } else if (position < this.length) {
        // 中间插入
        let index = 0;
        let currentNode = this.head;
        while (index < position) {
          index += 1;
          currentNode = currentNode.next;
        }
        newNode.next = currentNode;
        newNode.prev = currentNode.prev;

        currentNode.prev.next = newNode;
        currentNode.prev = newNode;
      } else {
        // 插入到最后
        this.tail.next = newNode;
        newNode.prev = this.tail;
        this.tail = newNode;
      }
    }

    // legnth + 1
    this.length += 1;
  };

  /**
   * 6. 获取节点
   * @param {number} position : ;
   * @returns
   */
  DoublyLinkedList.prototype.get = function (position) {
    // 1. 边界判断(类型判断就不做了 推荐使用ts)
    if (position < 0 || position > this.length) {
      return false;
    }
    // => 二分查找法
    // this.length / 2 > position 从头向后遍历
    // this.length / 2 < position 从后向前遍历

    let index = 0;
    let currentNode = this.head;
    while (index < position) {
      index += 1;
      currentNode = currentNode.next;
    }
    return currentNode.data;
  };

  /**
   * 7. 获取链表元素的 下标值
   * @param {any} data
   */
  DoublyLinkedList.prototype.indexOf = function (data) {
    let index = 0;
    let currentNode = this.head;
    while (currentNode) {
      if (currentNode.data == data) {
        return index;
      }
      index += 1;
      currentNode = currentNode.next;
    }

    return -1;
  };

  /**
   * 8. 修改列表中的元素
   * @param {number} position : ;
   * @param {any} data : ;
   */
  DoublyLinkedList.prototype.update = function (position, data) {
    // 1. 边界判断(类型判断就不做了 推荐使用ts)
    if (position < 0 || position > this.length) {
      return false;
    }

    let index = 0;
    let currentNode = this.head;

    while (index < position) {
      index += 1;
      currentNode = currentNode.next;
    }

    currentNode.data = data;
    return true;
  };

  /**
   * 9. 删除
   * @param {number*} position : ;
   * @returns
   */
  DoublyLinkedList.prototype.removeAt = function (position) {
    // 1. 边界判断
    if (position < 0 || position >= this.length) {
      return null;
    }

    // 和 inster 方法一样 需要判断多种情况
    let currentNode = this.head;

    // 2. 列表长度 == 1 的情况
    if (this.length == 1) {
      // 此情况 position 只能是 0  删除 第 0 个元素
      this.head = null;
      this.tail = null;
    } else {
      // 3. 列表长度 > 1 的情况
      // 3.1 删除第0个
      if (position == 0) {
        this.head = this.head.next;
        this.head.prev = null;
      } else if (position == this.length - 1) {
        // 删除最后一个
        currentNode = this.tail; // 为了能 返回删除的元素

        this.tail = this.tail.prev;
        this.tail.next = null;
      } else {
        let index = 0;

        while (index < position) {
          index += 1;
          currentNode = currentNode.next;
        }
        currentNode.prev.next = currentNode.next;
        currentNode.next.prev = currentNode.prev;
      }
    }

    this.length -= 1;

    return currentNode.data; // 返回删除的元素
  };

  /**
   * 10. 删除
   * @param {any} data
   * @returns
   */
  DoublyLinkedList.prototype.remove = function (data) {
    let index = this.indexOf(data);
    return this.removeAt(index);
  };

  DoublyLinkedList.prototype.isEmpty = function () {
    return this.length == 0;
  };

  DoublyLinkedList.prototype.size = function () {
    return this.length;
  };

  DoublyLinkedList.prototype.getHead = function () {
    return this.head;
  };

  DoublyLinkedList.prototype.getTail = function () {
    return this.tail;
  };
}
